package com.algrithom.tree.binarytree;

import java.util.Objects;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 543二叉树的直径
 */
public class Solution12 {
    
    private int ans = 1;
    
    public static void main(String[] args){
        Integer[] datas = new Integer[]{};
        TreeNode<Integer> root = TreeOperUtil.createTree(datas,0);
        Solution12 solution12 = new Solution12();
        System.out.println(solution12.diameterOfBinaryTree(root));
    }
    
    public int diameterOfBinaryTree(TreeNode<Integer> root){
        deep(root);
        return ans - 1;
    }
    
    private int deep(TreeNode<Integer> root){
        if (Objects.isNull(root)) {
            return 0;
        }
        int left = deep(root.getLeftChild());
        int right = deep(root.getRightChild());
        // 当前节点的最大直径
        ans = Math.max(ans,left + right + 1);
        // 左右结点的最大直径
        return Math.max(left,right) + 1;
    }
}
